#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//75.颜色分类
void sortColors(vector<int>& nums){
    //三个指针，left指针指向0区间最右侧，right指针指向2区间最左侧
    int left = -1, right = nums.size();
    //i指针用来遍历数组
    int i = 0;
    while(i<right){
        if(nums[i]==0){
            swap(nums[++left], nums[i++]);
        }
        else if(nums[i]==2){
            swap(nums[--right], nums[i]);
        }
        else{
            i++;
        }
    }
}

//912.排序数组
//随机取基准值
int getkey(int left,int right,vector<int>& nums){
    int r = rand();
    return nums[r % (right - left + 1) + left];
}
//分治递归快速排序
void quicksort(int l,int r,vector<int>& nums){
    if(l>=r){
        return;
    }

    int key = getkey(l, r, nums);

    int left = l - 1, right = r + 1;
    int i = l;

    while(i<right){
        if(nums[i]<key){
            swap(nums[++left], nums[i++]);
        }
        else if(nums[i]>key){
            swap(nums[--right], nums[i]);
        }
        else{
            i++;
        }
    }

    quicksort(l, left, nums);
    quicksort(right, r, nums);
}
vector<int> sortArray(vector<int>& nums){
    srand(time(NULL));

    quicksort(0, nums.size()-1, nums);

    return nums;
}


//215.数组中的第K个最大元素
//分治递归快速选择
int quicksort(int l,int r,vector<int>&nums,int k){
    if(l==r){
        return nums[l];
    }
    int key = getkey(l, r, nums);

    int left = l - 1, right = r + 1;
    int i = l;

    while(i<right){
        if(nums[i]<key){
            swap(nums[++left], nums[i++]);
        }
        else if(nums[i]>key){
            swap(nums[--right], nums[i]);
        }
        else{
            i++;
        }
    }

    //c是大于基准值区间的个数
    int c = r - right + 1;
    //b是等于基准值区间的个数
    int b = right - left - 1;

    //如果k小于c，则递归到大于基准值的子区间查找
    if(c>=k){
        return quicksort(right, r, nums, k);
    }
    //如果k小于b+c,则直接返回基准值
    else if((c+b)>=k){
        return key;
    }
    //都不满足，则递归到小于基准值的子区间查找
    else{
        return quicksort(l, left, nums, k - b - c);
    }
}
int findKthLargest(vector<int>& nums, int k){
    srand(time(NULL));

    return quicksort(0, nums.size() - 1, nums,k);
}

//面试题17.14最小的k个数
//分治递归快速选择
void _quicksort(int l,int r,vector<int>& nums,int k){
    if(l==r){
        return;
    }

    int key = getkey(l, r, nums);

    int left = l - 1, right = r + 1;
    int i = l;

    while(i<right){
        if(nums[i]<key){
            swap(nums[++left], nums[i++]);
        }
        else if(nums[i]>key){
            swap(nums[--right], nums[i]);
        }
        else{
            i++;
        }
    }

    //a表示小于基准值区间的个数
    int a = left - l + 1;
    //b表示等于基准值区间的个数
    int b = right - left - 1;

    if(a>=k){
        //当小于基准值区间的值大于等于K个数时，继续到对应的子区间递归查找
        quicksort(l, left, nums, k);
    }
    else if((a+b)>=k){
        //当小于等于基准值区间的值大于等于k个数时，直接结束返回
        return;
    }
    else{
        //当上面两种情况都不满足时，继续到大于基准值区间中查找k-a-b个数
        quicksort(right, r, nums, k);
    }

}
vector<int> smallestK(vector<int>& arr, int k){
    srand(time(NULL));

    _quicksort(0, arr.size() - 1, arr, k);

    return (arr.begin(), arr.begin() + k);
}



int main(){
    vector<int> nums = {5, 1, 1, 2, 0, 0};
    nums = sortArray(nums);
    for(auto num : nums){
        cout << num << " ";
    }

    return 0;
}